package main

import "math"

func max(x, y int) int {
	if x < y {
		return y
	}
	return x
}

func maxProfit(prices []int) int {
	// dp[i][k][0] 表示第 i 天, 经过最多 k 次交易, 不持有股票, 的最大收益
	// dp[i][k][1] 表示第 i 天, 经过最多 k 次交易, 持有股票, 的最大收益
	dp := make([][3][2]int, len(prices))
	dp[0][0][0] = 0
	dp[0][0][1] = -math.MaxInt
	dp[0][1][0] = 0
	dp[0][1][1] = -prices[0]
	dp[0][2][0] = 0
	dp[0][2][1] = -prices[0]
	n := len(prices)
	for i := 1; i < n; i++ {
		for k := 0; k < 3; k++ {
			if k == 0 {
				dp[i][k][0] = dp[i-1][k][0]
				dp[i][k][1] = dp[i-1][k][1] // k == 0 无法买入
			} else { // k > 0 可以买入
				dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i]) // 卖出
				dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i])
			}
		}
	}
	return dp[n-1][2][0]
}

func main() {
	println(maxProfit([]int{3, 3, 5, 0, 0, 3, 1, 4}))
	println(maxProfit([]int{1, 2, 3, 4, 5}))
	println(maxProfit([]int{7, 6, 4, 3, 1}))
}
